贪婪之罪：Q

2024-07-09 21:13| 来源: 网络整理| 查看: 265

这篇文章的目的是介绍 Q-learning 中两种有趣的 bias，它们产生的原因不同，但都会对智能体学习最优策略产生很大的影响。在利用 Q-learning 及其派生方法解决强化学习问题时，应当警惕这两种 bias。文章的主要内容可以简单分为四个部分：

什么是 Q-learning？（已熟悉 Q-learning settings 的同学可以直接跳过）过度乐观引起的 Upward Bias在妄想中疯狂的 Delusional Bias总结与讨论什么是 Q-learning？

Q-learning是强化学习里非常基础也非常重要的一个算法，是属于model-free、value-based、off-policy的一种方法。自 DeepMind 2015年在 Nature 杂志上发表 DQN（Human-level control through deep reinforcement learning）以来，深度强化学习逐渐在各个领域里取得了一定的成功，并且变得越来越热门（看看今年的 ICML 就知道啦~）。DQN 的成功正是建立在 Q-learning 的基础上，而后续这几年陆续被提出的很多先进的强化学习方法也是如此。

Q-learning，顾名思义，就是学习Q值，也即（状态-）动作价值，它表示遵循某个策略 $\pi$ 时，在某个状态下采取动作所能得到的期望回报，也即：

$Q_{\pi}(s, a)=\mathbb{E}_{\pi}\left[G_{t} \mid S_{t}=s, A_{t}=a\right]$

表示的是未来所能得到的总奖励，那当然是越高越好。我们在初始时刻并不知道准确的值，但通过与环境的不断交互，可以基于环境给与的反馈来学习出值。Q-learning的算法流程如下：

Figure 1: Q-learning

假设我们用一个 $\text{# of states} \times \text{# of actions}$ 的表格表示值，称作 Q-table。就像训练神经网络时初始化模型系数一样，我们首先会初始化这个表格。然后开始与环境进行交互，以游戏为例。一局（一个 episode）内有很多个 step，我们会做一系列的动作，并最终获得胜利/失败（到达结束状态）。在每一个 step 中，接收到当前状态后，我们就根据当前的 Q-table 选出值最大的动作（也有可能用 $\epsilon\text{-greedy}$ 以一定概率随机选动作），执行该动作后，会从环境获得即时奖励和转移到的下一 step 的状态。

由于我们不知道真实的值是多少（不像监督学习那样有label），我们就需要构建一个估计出来的 Q-target（绿色框部分）。像 TD(0) 一样，Q-learning 每次只往前看一步，它会利用执行当前动作后收到的即时奖励和对转移到的状态的最大值来构造 Q-target。直观一点来说就是，马上能得到的，确定的奖励是，估计未来能得到的最大奖励则是 $\max _{a} Q\left(S^{\prime}, a\right)$ ，那定下一个小目标，就让当前估计的 Q(S, A) 能往这两者之和靠拢吧！

随着与环境的交互，随着一次次迭代，这个小目标会带领算法收敛到正确的值，得到最优的策略。但恰恰也是这个贪婪的小目标，为 Q-learning 带来了很多问题。

过度乐观引起的 Upward Bias

Upward Bias，或者说 Overestimation 问题最早是在1993年由 Sebastian Thrun 和 Anton Schwartz 两位学者提出（论文："Issues in Using Function Approximation for Reinforcement Learning"），他们观察到 Q-learning 会有高估动作价值（值）的倾向，并将此问题归因为函数近似器不够灵活。而 Hado van Hasselt 在 NeurIPS 2010 上发表的 "Double Q-learning" 一文则进一步发现，即便是在 tabular setting 下（不考虑函数逼近，直接学习 Q-table），若环境包含噪声（随机性环境），那么 Q-learning 也会导致高估问题。这两篇论文都对 Q-learning 中的高估问题进行了很好的分析，在此基础上 DeepMind 在 AAAI 2016 上发表了 "Deep Reinforcement Learning with Double Q-Learning"，真正地统一了引起 Upward Bias 的原因：

Estimation errors of any kind can induce an upward bias, regardless of whether these errors are due to environmental noise, function approximation, non-stationarity, or any other source. This is important, because in practice any method will incur some inaccuracies during learning, simply due to the fact that the true values are initially unknown.

任何形式的估计误差都会招致 upward bias，误差可以来源于环境噪声也可以来自于函数逼近器自身或者别的各种原因。在初始学习时，我们并不知道真实的值是多少，只能通过和环境交互来逐步了解，所以误差是不可避免的。这里通过论文给出的一个例子来具体说明：

Figure 2: Illustration of over-estimations during learning.

这里我们考虑一种简化的情况，状态是连续的，在每个状态下能执行的动作有10种，并且他们真实的值都一样，也即对任意状态和动作均有 Q_*(s,a) = V_*(s) ，动作价值仅与状态有关，可以表达为状态的函数。

首先看上图的第一列，紫色线代表 Q_*(s,a) ，第一行中 $Q_*(s,a) = \sin{(s)}$ ，第二三行中 $Q_{*}(s, a)=2 \exp \left(-s^{2}\right)$ 。假设 $Q_{*}(s, a)$ 是已知的，我们采样出11个点（绿色实心点），然后直接用 degreed 为的多项式进行拟合，第一二行中 d=6 ，第三行则 d=9 ，拟合得到的结果用绿色线表示，我们也可以认为这是对值的估计 Q_t(s,a) 。在上面两行中， d=6 的多项式（对于不够灵活的函数逼近器）没能完全拟合所有点，而第三行 d=9 的多项式（对应足够灵活的函数逼近器）则完全拟合了。但无论是那种情况，在采样点以外的区域，总会对值存在高估（红色圈内）或低估的问题。

再来看第二列，对应于第一列，第二列是对10个动作都尝试了拟合（10条绿线），当然，每条线都是基于不同的样本拟合出来的。黑色虚线是将这10条线的最大值标识出来，也即 $\max_a Q_t(s,a)$ 。可以看到在考虑更多动作之后，高估问题更加严重了。第三列是将黑色虚线减去紫色线得到的，也即 $\max_a Q_t(s,a) - \max_a Q_*(s,a)$ ，我们可以更直观地看到高估了多少。蓝色线则是使用 Double Q-learning 的效果（几乎没有高估），不过我不准备在这篇文章里展开。

这个例子很好地展示了，即使我们知道真实的值，可以直接对照着它来学习，由于学习本身的误差，自然地会出现高估（无论函数逼近器是否足够灵活）。而当我们考虑多个动作，在所有估计值中取 max，高估问题就会被进一步放大。再回到 Q-learning 中，我们事先并不知道 Q_*(s,a) ，更新估计值 Q_t(s,a) 时设定的目标是基于另一个状态的最大估计值 $\max _{a} Q\left(s_{t+1}, a\right)$ 的，若对 $\max _{a} Q\left(S^{\prime}, a\right)$ 的估计本来就过分乐观（overoptimistic），那么更新的 时就会更一步地传播这种过度的乐观（overoptimism）。听起来挺积极向上的，但事实上，这种乐观精神的传递可能会鼓励算法错误和盲目地探索那些奖励没那么多的状态，并因此影响收敛甚至产生较差的策略。

小结一下，由于我们总是贪婪地采用最大估计值来更新值，于是高估动作价值的误差会被层层传播，这就是 upward bias 的由来。

在妄想中疯狂的 Delusional Bias

相比 upward bias，对 delusional bias 的研究就新鲜多了，直到 2018 年它才被准确地揪出。这个概念源于 NeurIPS 2018 的最佳论文 "Non-delusional Q-learning and Value Iteration"，ICML 2020 有它的后续研究 "ConQUR: Mitigating Delusional Bias in Deep Q-learning"。私以为这个名字取得是极好的，Delusional Bias，妄想偏差，比 Upward Bias 酷炫多了。用一句话概括就是：

Delusional bias occurs whenever a backed-up value estimate is derived from action choices that are not realizable in the underlying policy class.

一开始看这句话的时候我也没有很理解，其实说的是很直观的。通过下面这个例子，我们会清晰地认识到妄想偏差的由来：

Figure 3: A example for the delusional bias problem

截图来自 Tyler Lu 在 NeurIPS 2018 上的 Oral Presentation。这里以一个只有3个状态的 MDP 为例，状态1和2都可以执行 a, b 两个动作，但获得的奖励不同。在状态1执行动作 a 能得到＄50，执行动作 b 则会被扣除＄50，在状态2则恰恰相反。状态3可以执行的是 c, d 两个动作，执行动作 c 会以一定的概率转移到状态1或2，执行动作 d 则马上得到＄1。

直观上来看，人类很快就能得到这个 MDP 的最佳策略，在状态3时执行动作 c 以转移到可以获得＄50的状态1或2。在状态1我们会执行动作 a 拿下＄50，在状态2我们会执行动作 b 拿下＄50。假设我们用一个线性近似器来学习值，只有一个参数 $\theta$ ，输入是状态-动作对的特征 $\phi(s, a)$ ，并且已知 $\phi(1, a)=\phi(2, a)=1$ 和 $\phi(1, b)=\phi(2, b)=-1$ 。

很明显，当 $\theta0$ 时，在状态1会选择动作 a 拿到＄50，在状态2也会选择动作 a 被扣除＄50， $\theta0$ 时则相反。这是模型本身带来的限制，它无法做到人类能做的最佳策略。但即便如此，理论上能学到的最优策略也是前者，因为在状态3下转移到状态1的概率高达0.9，选择执行动作 a 大概率能让我们拿到＄50而不是丢掉＄50，此时在状态3下执行动作 c 的期望奖励应该是＄40，比执行动作 d 的＄1要高得多。

遗憾的是，Q-learning 很可能学不到这个理论上最优的策略。因为在学习 $Q(1, \cdot)$ 时，算法会把 $\theta$ 推高以增加 Q(1, a) 和降低 Q(1, b) ，但这同时也降低了 Q(2, b) 的估计；而在学习 $Q(2, \cdot)$ 时，算法又会反过来把拉低以增加 Q(2, b) 和降低 Q(2, a) ，并同时降低了 Q(1, a) 的估计。来回的拉扯最终会使 Q(1, a) = Q(1, b) = Q(2, a) = Q(2, b) = 0 （注：在该例子中，作者假设了“we sample all the transitions roughly uniformly”）。从而让 Q(3, d) = 1 Q(3, c) =0 ，得到的策略是在状态3执行动作 d 获得＄1，得到的奖励远差于最优策略。

小结一下，产生 delusional bias 的根本原因是函数近似器的表达能力有限，但它自己并不自知。在学习的过程中，它总是贪婪地想要获取最大利益，妄想自己能同时做到并不相容的事情（比如上述例子中同时在状态1选择动作 a 和在状态2选择动作 b）。

总结与讨论

总结一下，这篇文章介绍了 Q-learning 中两种有趣的 bias，也即 upward bias 和 delusional bias，并通过例子进一步诠释它们产生的原因。当我们尝试解决一些现实问题，或在一些复杂环境中使用 Q-learning 或 DQN 等延伸方法时，除了调参，我们也需要注意这两种 bias 对效果的影响，对症下药才能炼出好丹~

这里抛出几个问题，欢迎大家留言讨论：

如何甄别训练过程中出现了 upward bias 和 delusional bias？使用 On-policy 的学习方法是否还会出现 upward bias 和 delusional bias？Double Q-learning 是如何解决 upward bias 问题的？Delusional bias 是否是一个常见问题？使用更强的函数逼近器能解决吗？

最后，如果这篇文章有帮助到你理解这两种bias，欢迎点赞、关注、收藏，素质三连。

P.S. 封面图来自《猎人》贪婪之岛（Greed Island）篇，动漫有点老了，刚好切题就拿来当封面了哈哈。

【本文地址】

贪婪之罪：Q

贪婪之罪：Q

今日新闻

推荐新闻